package com.example.demo.leetcode.jianzhi;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 *
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 B：
 *
 *    4
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 示例 1：
 *
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 *
 * @date 2021/7/19 17:14
 */
public class Btree_树的子结构 {

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }

    public boolean isSubStructure(TreeNode A, TreeNode B) {

        List<Integer> most = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        midlle(most,A);
        midlle(subList,B);

        if(most.size()==0 || subList.size() ==0){
            return false;
        }

        if(most.size()>=subList.size()){
            for(int i=0;i<most.size();i++){
                if(most.get(i) == subList.get(0)){
                    if(compare(most,subList,i,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean compare(List<Integer> most,List<Integer> subList,int i,int j){
         int len = subList.size();
         for(int k=0;k<=len;k++){
             if(k == len){
                 return true;
             }
             if(i+k>=most.size()){
                 return false;
             }
            if(most.get(i+k) == subList.get(j+k)){
                continue;
            }
            return false;
         }
         return false;
    }


    public void midlle(List<Integer> list,TreeNode root){

         if(root == null){
             return;
         }
         midlle(list,root.left);
         list.add(root.val);
         midlle(list,root.right);
    }


    //中序遍历无法处理null问题，采用递归处理
    public boolean isSubStructure2(TreeNode A, TreeNode B) {
         if(A==null || B==null){
             return false;
         }
        return middaA(A,B);
    }

    public boolean middaA(TreeNode root,TreeNode B){
         if(root == null){
             return false;
         }

         boolean f1 = compare(root,B);
         boolean f2 = middaA(root.left,B);
         boolean f3 = middaA(root.right,B);
        return f1 || f2 || f3;
    }

    public boolean compare(TreeNode A, TreeNode B){
         if(A == null && B == null) return true;
         if(A == null && B!= null) return false;
         if(A != null && B==null) return true;
         if(A.val == B.val){
             return compare(A.left,B.left) && compare(A.right,B.right);
         }
         return false;
    }




}
